package utils;


import java.util.Iterator;

import java.util.Vector;

import env.City;
import env.DistList;
import env.Road;
import env.World;

public class Dijkstra {
	/**
	 * return a sorted vector of city distances
	 * 
	 * @param world
	 * @param init
	 * @param ignoreBlocked
	 * @return
	 */
	public static DistList runDijkstra(World world, City init,
			boolean ignoreBlocked) {//TODO matan modify dijkstra to return a distlist with correct parrent nodes
		
		DistList distances = new DistList(world, init);
		Vector<City> visited = new Vector<City>();
		Vector<City> queue = new Vector<City>();
		queue.add(init);
		while (queue.size() > 0) {
			Iterator<City> it = queue.iterator();
			City u = null;
			int d = Integer.MAX_VALUE;
			while (it.hasNext()) {
				City t = it.next();
				int tDist = distances.getDistance(t);
				if (tDist <= d) {
					d = tDist;
					u = t;
				}
			}
			visited.add(u);
			queue.remove(u);
			Iterator<Road> rit = u.getRoads().iterator();
			while (rit.hasNext()) {

				Road r = rit.next();
				if (ignoreBlocked) {
					while (r.isBlocked())
						r = rit.next();
				}
				City v = r.getNeighbor(u);
				int alt = d + r.getCost();
				if (alt < distances.getDistance(v) && !visited.contains(v)) {
					distances.setDistance(u, v, alt);
					queue.add(v);
				}
			}
		}
		distances.sort();
		return distances;

	}
}
